﻿using System;

namespace Lesson14_选择排序
{
    class Program
    {
        static void Main(string[] args)
        {
            #region 选择排序基本原理
            //总共进行(arr.Lengh - 1)轮排序
            //每轮排序找到最大的一项将其放到最后一位
            //通过一个中间变量 先让它等于0  即第一项 向后比较 若遇到比第一项大的 就将中间变量的值改为当前项的下标
            #endregion

            #region 代码实现
            //将下面的数组升序排列
            int[] arr = { 3, 5, 7, 9, 8, 6, 4, 2, 1 };
            //第一步
            //申明中间变量
            int index = 0;
            //申明临时变量用于数组项的交换
            int temp = 0;
            //第二步
            //总共进行arr.Length - 1轮
            for (int i = 0; i < arr.Length - 1; i++)
            {
                //每轮开始前将index置0
                index = 0;
                //第三步
                //找到最大的一项
                //i 从 1 开始 因为arr[index]不必和自己比较
                for(int j = 1; j < arr.Length - i; j++)
                {
                    if (arr[index] < arr[j])
                    {
                        //找到最大项的下标
                        index = j;
                    }
                }
                //优化一：若最大值恰好在最后，那么就不必交换
                if (index == arr.Length - 1 - i)
                {
                    continue;
                }
                //找到后 将最大值与该轮的最后一项交换
                temp = arr[index];
                arr[index] = arr[arr.Length - 1 - i];
                arr[arr.Length - 1 - i] = temp;

            }


            //打印
            for (int i = 0;i < arr.Length; i++)
            {
                Console.WriteLine(arr[i]);
            }
            #endregion

            //选择排序模版
            //1.申明中间变量和临时变量
            //2.外层循环 进行arr.Length - 1轮
            //3.内层循环开始前将中间变量置0，每次循环arr.Length - i(冒泡排序为arr.Length - 1 - i)
            //4.优化 内层循环结束后判断 若最大值恰好在最后 那么就不必再交换
            //5.交换
        }
    }
}